home *** CD-ROM | disk | FTP | other *** search
/ Aminet 1 (Walnut Creek) / Aminet - June 1993 [Walnut Creek].iso / aminet / util / pack / xpkrdcn21.lha / xpkRDCN / compr.asm next >
Assembly Source File  |  1993-04-10  |  11KB  |  314 lines
  1. ;---------------------------------------------------------------------------;
  2. ;                                        ;
  3. ; This is the Ross Data Compression implemented in 68000 assembler          ;
  4. ; by Niklas Sjöberg, 2:203/415.3@Fidonet                    ;
  5. ;                                        ;
  6. ;                                        ;
  7. ; The source is fully in the Public Domain. If you think you can improve    ;
  8. ; some parts, feel free to modify the code. HOWEVER, be carefull to comment ;
  9. ; the parts where you change!                            ;
  10. ;                                        ;
  11. ; On entry (if you compre to the C-code):                    ;
  12. ;                                        ;
  13. ; a0 = ctrl_idx, pointer to 'outbuff' where the 16 bits control-word is     ;
  14. ;      stored after each 16th sequence. On startup, ctrl_idx is set to      ;
  15. ;      the start of 'outbuff' and 'outbuff' is advanced two bytes.        ;
  16. ; a1 = in_idx, pointer to next byte of input                    ;
  17. ; a2 = out_idx, pointer to 'outbuff'                        ;
  18. ; a3 = inbuff_end, end of input buffer (could you guess? :)            ;
  19. ; a4 = anchor, temporary pointer to in_idx, undefined on entry!            ;
  20. ; a5 = pat_idx, temporary pointer to pattern in dictionary, undefined on    ;
  21. ;      entry!                                    ;
  22. ; a6 = hash_tbl (uchar **hash_tbl) pointer. Size is 16K, just enough for    ;
  23. ;      4096 pointers.                                ;
  24. ; d0 = ctrl_cnt, used to keep track of when control-word is to be written   ;
  25. ;      to ctrl_idx. (every 16th sequence). Start at 1(!), counts to 16      ;
  26. ;      0 one startup, but note that d0 is increased by one _before_ it      ;
  27. ;      actually is used.
  28. ; d1 = c. Stores various chars when comparing source and destination.       ;
  29. ;      always byte-size. Zero on startup.                    ;
  30. ; d2 = cnt. Stores different values. Used as a 'quick counter' instead of   ;
  31. ;      subtracting to addresses. Zero on startup.                ;
  32. ; d3 = ctrl_bits, 16 bit compression code. Zero on startup.            ;
  33. ; d4 = gap. Used as counter to see if pattern occured with 4098 range.      ;
  34. ;      Zero on startup.                                ;
  35. ; d5 = hash. 16 bit hash-value used as dictionary lookup. Always in range   ;
  36. ;      from 0 to 4095. Zero on startup.                        ;
  37. ; d6 = outbuff_end, end of 'outbuff'. If we exceed this limit (actually we  ;
  38. ;      have a 48 byte margin) data couldn't be compressed!            ;
  39. ;                                        ;
  40. ;                                        ;
  41. ;---------------------------------------------------------------------------;
  42. ; Since both a4 and a5 just are used temprarily they're used as temporary   ;
  43. ; scratch in some places. Similary d5 (hash) and d7 are used as scratch     ;
  44. ;---------------------------------------------------------------------------;
  45. ;
  46. ;
  47. ; Version changes:
  48. ; 921205 - ctrl_cnt (d0) now count from 16 and downwards. Slightly faster.
  49. ;          Now uses bset instead of asl and or.
  50. ; 921205 - Due to optimizing all comments may not be totally accurate. Ie.
  51. ;          you have to read 5 lines at a time in order to understand the
  52. ;          comments..
  53. ; 930325 - Some optimizations by John Harris - jharris@cup.portal.com
  54. ;          All new opts marked with a '@'.  Cycle savings at 68000 level:
  55. ;        - Changed branches in ploop, and replaced "tst, bne, sub" with "dbf"
  56. ;          Saved 14.25 cycles per loop.
  57. ;     - RLE check 20-74 cycles faster when RLE fails, or 52 + 38 per loop
  58. ;          when RLE is successful
  59. ;        - Pattern check is an additional 12 faster, plus 48 per loop
  60. ; 930409 - (Niklas Sjoberg) Fixed some lethal bugs. Might take a few more
  61. ;          cycles but compression won't be safe otherwise!
  62.  
  63.  
  64.     xdef    _pack_one        ; only one routine, called from the
  65.                     ; C-part of the library
  66.  
  67.     INCLUDE "libraries/xpksub.i"
  68.  
  69.     section    code
  70.  
  71. _pack_one
  72.     movem.l    a2-a6/d2-d7,-(SP)    ; Save non-scratch registers
  73.  
  74.     moveq    #16,d0
  75.     moveq    #$0,d1
  76.     moveq    #$0,d2
  77.     moveq    #$0,d3
  78.     moveq    #$0,d4
  79.     moveq    #$0,d5
  80.     moveq    #$0,d7
  81.  
  82.     suba.l    a4,a4            ; not necessary, but may help debugging.
  83.     suba.l    a5,a5
  84.     bra.s    pstart            ; @ Make spot to place exit sections so
  85. ;                    ;   some branches can be made short, or
  86. ;                    ;   made to fall through most of the time
  87. ;                    ; @ Moved overflow and ploop_end here
  88. overflow
  89.     moveq    #0,d0            ; If overflow the C-code will return
  90.     bra.s    p_exit            ; XPKERR_EXPANSION
  91. ;                    ; This and ploop_end are the only exit points
  92.  
  93. ploop_end
  94.                     ; We ran out of buffer, phew!
  95. ;    move.w    #16,d7            ; make sure the last control bits
  96. ;    sub.w    d0,d7            ; are written to ctrl_idx first-
  97. ;    asl.w    d7,d3
  98.  
  99. ;    move.w    d3,(a0)            ; *ctrl_idx = ctrl_bits
  100.  
  101.     move.b    d3,1(a0)        ;store controlword
  102.     asr.w    #8,d3            ; Now works with 68000 as well..
  103.     move.b    d3,(a0)
  104.  
  105.     move.l    a2,d0            ; return out_idx, on error (overflow)
  106. p_exit    movem.l    (SP)+,a2-a6/d2-d7    ; we return 0
  107.     rts
  108.  
  109. pstart
  110. ;    move.l    d0,-(SP)
  111. ;    move.l    a3,d0
  112. ;    sub.l    a1,d0
  113. ;    cmp.l    #8170,d0
  114. ;    bhi    cont
  115. ;    nop
  116. cont
  117. ;    move.l    (SP)+,d0
  118.     cmpa.l    a1,a3            ; Main-loop, running as long as in_idx
  119.     bls.s    ploop_end        ; doesn't exceed outbuff_end.
  120.  
  121. ;    tst.b    d0            ; @Is it time to write controlbits into
  122. ;    bne.s    no_makeroom        ; @ctrl_idx?
  123.     dbf    d0,no_makeroom        ; @ Replaced above two lines, and
  124. ;                    ;   subq #1 later, with this DBF
  125.  
  126. ;    move.w    d3,(a0)            ; store control-word and
  127.     move.b    d3,1(a0)        ;Now works on 68000
  128.     asr.w    #8,d3
  129.     move.b    d3,(a0)
  130.  
  131.     moveq    #0,d3
  132.     moveq    #15,d0            ; advance out_idx two bytes.
  133.     move.l    a2,a0            ; but first store address where
  134.     addq.w    #2,a2            ; the next word is to be written
  135.     cmp.l    d6,a2            ; Make sure there is no overflow.
  136.     bhi.s    overflow        ; @ Chg branch priority  out_idx really should be < outbuff_end :)
  137.  
  138. no_makeroom
  139. ;    subq.b    #1,d0            ; @ Deleted
  140. ;                                       ; @ Deleted label "no_overflow"
  141.  
  142.     move.l    a1,a4            ; Use anchor = in_idx
  143.     move.b    (a1)+,d1        ; First byte to compare. in_idx is advanced
  144.     cmp.b    (a1)+,d1            ; @ Since most of the time will not be
  145.     bne.s   n_rleseq        ;   rle, I put two compares outside
  146.     cmp.b    (a1)+,d1        ;   the loop, for much less overhead
  147.     bne.s    n_rleseq        ;   and elimination of cmpi.w #2 later
  148.     cmp.l    a1,a3
  149.     bcs.s   cant_compress        ; @ less than 3 bytes left in inbuff
  150.  
  151. ;                ; @ Deleted old rep1 loop
  152. ;    moveq    #1,d2
  153. ;rep1
  154. ;    cmp.b    (a1),d1            ; Does next char match the one before
  155. ;    bne.s    nrep
  156. ;    cmp.w    #4114,d2        ; Make sure we don't exceed the longest
  157. ;    bge.s    nrep            ; possible RLE
  158. ;    cmpa.l    a1,a3            ; Make sure we're not running out of source
  159. ;    bls.s    nrep
  160. ;    addq.w    #1,a1            ; Bytes obviously was equal, advance in_idx
  161. ;    addq.w    #1,d2            ; to next byte.
  162. ;    bra.s    rep1
  163.  
  164. ;nrep    cmpi.w    #$2,d2            ; @ Deleted - cnt<3 handled outside loop
  165. ;    bls.s    n_rleseq                ; @
  166.  
  167. ;                ; @ rep1 now counts down from 4111.  Adjusted
  168. ;                ;   after loop to # of cnts past 3.  This is
  169. ;                               ;   over twice as fast as the old loop.
  170.  
  171.     move.w    #4111,d2
  172.     move.w    d2,d7
  173. rep1
  174.     cmpa.l    a1,a3
  175.     bls.s    nrep        ; @ If exited on cmp with inbuff_end, adrs & cnt
  176.     cmp.b    (a1)+,d1
  177.     bne.s   adj_a1
  178.     dbf    d7,rep1
  179. ;                ;   are correct.
  180.     moveq    #0,d7        ; @ Otherwise, both need to be adjusted by 1
  181. adj_a1    subq.w    #1,a1            ; @ a1 is one higher than it should be
  182. ;                    ;   because of post index
  183. nrep    sub.w    d7,d2            ; @ Adjust d2 = # of cnts past 3
  184.     cmpi.w    #15,d2            ; @ adjusted for new d2
  185.     bgt.s    l_rlen            ; if cnt <= 18 we use short form of RLE
  186. ;    subq.b    #3,d2            ; @ Deleted.  count, at least three chars
  187.     move.b    d2,(a2)+
  188.     move.b    d1,(a2)+        ; the character itself
  189.     bset    d0,d3
  190. ;    asl.w    #1,d3            ; Shift and set control bits
  191. ;    or.w    #1,d3
  192.     bra.s    pstart            ; re-start loop, until in_idx => outbuff_end
  193.  
  194. l_rlen                    ; If cnt > 18 we encode a long RLE (max 4114 chars)
  195.     sub.w    #16,d2            ; @ Adjusted.  cnt -= 19, at least 19 repeated chrs
  196.     move.b    d2,d7            ; out_idx++ = 16 + (cnt & 0x0F) Store low count
  197.     and.b    #15,d7            ; and code
  198.     add.b    #16,d7
  199.     move.b    d7,(a2)+
  200.  
  201.     asr.w    #4,d2            ; out_idx++ = cnt >> 4
  202.     move.b    d2,(a2)+        ; and store high count
  203.     move.b    d1,(a2)+        ; the character itself
  204.  
  205. ;    asl.w    #1,d3            ; Just like above, set and shift
  206. ;    or.w    #1,d3
  207.     bset    d0,d3
  208.     bra.w    pstart
  209.  
  210. ;                ; @ Moved cant_compress here to make the best
  211. ;                ;   use of short branches
  212.  
  213. cant_compress
  214.     move.b    d1,(a2)+        ; Data couldn't be compressed so
  215. ;    addq.l    #1,a4            : just copy to out_idx, and set
  216. ;    move.l    a4,a1            ; in_idx to next byte of data
  217.     lea    1(a4),a1
  218. ;    asl.w    #1,d3            ; Do NOT set control bit, just shift
  219.     bra.w    pstart
  220.  
  221. n_rleseq
  222. ;                ; @ ALERT This check was changed to .w, because
  223. ;                ;   the input buffer size is <64K.  This is
  224. ;                ;   faster, but needs to be changed back to .l
  225. ;                ;   if inbuff will ever be increased above 64K
  226.     move.w    a3,d5            ; inbuff_end - in_idx > 2
  227.     sub.w     a4,d5            ; we must have at least 3 characters left in
  228.     subq.w    #$2,d5            ; @ chg cmpi to subq.  order to calc the hash.
  229.     bls.s    cant_compress        ; if less bytes left, just copy them
  230.     move.l    a4,a1            ; in_idx = anchor, restore to original start
  231.     moveq    #0,d5            ; hash
  232.     moveq    #0,d7            ; scratch
  233.  
  234. ; Now lets calculate the hash, in C this is done as:
  235. ; unsigned short int hash = ((((in_idx[0] & 15) << 8) | in_idx[1]) ^
  236. ; ((in_idx[0] >> 4) | (in_idx[2] << 4))) & 4096-5
  237. ;
  238. ; cnt (=d2) is used as scratch here..
  239.  
  240.     move.b    (a1)+,d5        ; @ chged to '(a1)+' in_idx[0] & 15 << 8
  241.     move.b    d5,d7            ; in_idx[0]
  242.     and.b    #15,d5
  243.     asl.w    #8,d5
  244.     or.b    (a1)+,d5        ; @ '+'   | in_idx[1]
  245.     asr.b    #4,d7            ; ^ in_idx[0] >> 4
  246.     moveq    #0,d2            ; gee, almost ran out of registers :)
  247.     move.b    (a1)+,d2        ; @ '+'   in_idx[2] << 4
  248.     asl.w    #4,d2
  249.     or.w    d2,d7
  250.     eor.w    d7,d5
  251.     and.w    #4096-1,d5
  252.     asl.w    #2,d5            ; char * is 4 bytes, adjust offset
  253.     move.l    a4,a1            ; @ Restore a1
  254.  
  255.  
  256. ; The zero here is used in order to stop SAS asm from stupid complaining!
  257.  
  258.     move.l    0(a6,d5.w),a5        ; pat_idx now zero or pointer to pattern
  259.     move.l    a1,0(a6,d5.w)        ; store in_idx at this offset
  260.  
  261.     move.l    a1,d4            ; gap = in_idx - pat_idx, ie. if
  262.     move.l    a5,d7            ; pat_idx was zero, gap will be huge
  263.     sub.l    d7,d4            ; which showed that we didn't find
  264.     cmp.l    #4098,d4        ; a pattern. That's why .l is used here!
  265.     bgt.s    cant_compress
  266.     move.w    #271,d2            : @ chged loop to count from 271 down
  267.     move.w    d2,d7            ; @
  268. rep2
  269.     cmpa.l    a5,a4            ; and pat_idx doesn't advance into the source!
  270.     bls.s    nrep2            ; this is VERY important!!
  271.     cmpa.l    a1,a3            ; While we don't run out of source..
  272.     bls.s    nrep2        ; @ If exited on cmp with inbuff_end, adrs & cnt
  273.     cmpm.b    (a5)+,(a1)+        ; @ Changed to cmpm.b
  274.     bne.s   adj2_a1
  275.     dbf    d7,rep2            ; @ chged to dbls
  276. ;                ;   are correct.
  277.     moveq    #0,d7        ; @ Otherwise, both need to be adjusted by 1
  278. adj2_a1    subq.w    #1,a1            ; @ a1 is one higher than it should be
  279.  
  280. nrep2    sub.w    d7,d2
  281.     cmpi.w    #2,d2            ; If cnt <= 2 we can't compress!
  282.     bls.s    cant_compress        ; @ Changed to .s
  283.     subq.w    #3,d4            ; gap -= 3, at least length of three
  284.     cmpi.w    #15,d2            ; if cnt <= 15 we encode as short pattern
  285.     bgt.s    is_lpat
  286.     asl.b    #4,d2            ; *out_idx++ = (cnt << 4) + (gap & 0x0F)
  287.     move.b    d4,d7            ; store count (low) and low offset
  288.     and.b    #15,d7
  289.     add.b    d7,d2
  290.     move.b    d2,(a2)+
  291.     asr.w    #4,d4            ; *out_idx++ = gap >> 4
  292.     move.b    d4,(a2)+        ; store high offset in hash-table
  293. ;    asl.w    #1,d3            ; set and shift control-bits
  294. ;    or.w    #1,d3
  295.     bset    d0,d3
  296.     bra.w    pstart            ; back to main-loop
  297.  
  298.  
  299.                     ; cnt > 15 so encode as long pattern
  300. is_lpat
  301.     move.b    d4,d7            ; *out_idx++ = 32 + (gap & 0x0F)
  302.     and.b    #15,d7            ; store 2 (low) and low offset
  303.     add.b    #32,d7
  304.     move.b    d7,(a2)+
  305.     asr.w    #4,d4            ; *out_idx++ = gap >> 4
  306.     move.b    d4,(a2)+        ; store high offset
  307.     sub.w    #16,d2            ; *out_idx++ = cnt - 16;
  308.     move.b    d2,(a2)+        ; store count (since length is at least
  309.                     ; 16 we can subtract 16 and thus handle
  310.                     ; patterns <= 271
  311.     bset    d0,d3
  312.     bra.w    pstart
  313.     END
  314.